package aufgabe1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Graph {

	private static AdjacencyStructure _adjStructure;
	private static Graph g = new Graph();
	private static ArrayList<Edge> _edges;
	private static ArrayList<Vertice> _vertices;
	private static int[][] _matrix;
	private static LinkedList<Edge>[] liste;
	private ArrayList<Vertice> path;
	private Queue<Edge> closeList;
	private Queue<Edge> openList;

	// private MaxSpannbaum max;

	public Graph() {

	}

	public static void createGraph(String filename,
			AdjacencyStructure.Type adjStructure) {

		g.readFile(filename);

		switch (adjStructure) {
		case LIST:
			_adjStructure = new AdjacencyList(g);
			createList();

			break;
		case MATRIX:
			_adjStructure = new AdjacencyMatrix(g);
			g.createMatrix();
			break;
		}

	}

	public boolean hasClosedEulerPath() {
		boolean closed = false;
		for (int i = 1; i < _vertices.size(); i++) {
			if (getNeighbours(i).size() % 2 == 0) {
				closed = true;
			} else {
				return false;
			}
		}
		return closed;
	}

	/**
	 * Definition offener euler pfad: Pfad hat entweder genau 2 ungerade knoten
	 * oder garkeine(geschlossen)
	 * 
	 * @return
	 */
	public boolean hasOpenEulerPath() {
		int quantityOfUnevens = 0;
		for (int i = 1; i < _vertices.size(); i++) {
			if (getNeighbours(i).size() % 2 == 0) {
				// geschlossener noch vorhanden
			} else {
				quantityOfUnevens++;
				if (quantityOfUnevens > 2) {
					return false;
				}
			}
		}
		// wenn hier angekommen, ist der euler geschlossen
		return true;
	}

	public ArrayList<Vertice> getEulerPathThroughGraph(int startNode) {
		path = new ArrayList<Vertice>();
		closeList = new LinkedList<Edge>();
		openList = new LinkedList<Edge>();

		if (this.hasClosedEulerPath()) {
			System.out.println("Graph has an closed euler");
			openList.addAll(getEdges());
			// System.out.println(openList);
			path.add(new Vertice(startNode));
			this.getClosedEulerPathThroughGraph(startNode);
			return path;

		} else if (this.hasOpenEulerPath()) {
			System.out.println("Graph has an open euler");
			openList.addAll(getEdges());
			path.add(new Vertice(startNode));
			this.getOpenEulerPathThroughGraph(startNode);
			return path;
		} else {
			return null;
		}

	}

	private boolean getClosedEulerPathThroughGraph(int startNode) {
		Queue<Vertice> neighbours = new LinkedList<Vertice>();
		boolean wasSuccessful = false;

		// fill with neighbours
		neighbours.addAll(getNeighbours(startNode));

		Vertice cur;
		while ((cur = neighbours.poll()) != null) {

			if (openList.isEmpty()) {

				return true;
			}

			// problem: erkennung von eindeutiger kante mit gegebenen werten
			Edge e = new Edge(new Vertice(startNode), cur, 1); // hin
			Edge e2 = new Edge(cur, new Vertice(startNode), 1); // zurueck

			if (openList.remove(e) && openList.remove(e2)) {
				closeList.add(e);
				closeList.add(e2);

				path.add(cur);
				wasSuccessful = getOpenEulerPathThroughGraph(cur.getPos());

				if (!wasSuccessful) {
					openList.add(e);
					openList.add(e2);
					closeList.remove(e);
					closeList.remove(e2);
					path.remove(path.size() - 1);
					wasSuccessful = false;

				}

			}
		}

		return wasSuccessful;
	}

	private boolean getOpenEulerPathThroughGraph(int startNode) {
		Queue<Vertice> neighbours = new LinkedList<Vertice>();
		boolean wasSuccessful = false;

		// fill with neighbours
		neighbours.addAll(getNeighbours(startNode));

		Vertice cur;
		while ((cur = neighbours.poll()) != null) {
			if (openList.isEmpty()) {
				return true;
			}
			Edge e = new Edge(new Vertice(startNode), cur, 1); // hin
			Edge e2 = new Edge(cur, new Vertice(startNode), 1); // zurueck

			if (openList.remove(e) && openList.remove(e2)) {

				closeList.add(e);
				closeList.add(e2);

				path.add(cur);
				wasSuccessful = getOpenEulerPathThroughGraph(cur.getPos());

				if (!wasSuccessful) {
					openList.add(e);
					openList.add(e2);
					closeList.remove(e);
					closeList.remove(e2);
					path.remove(path.size() - 1);
					wasSuccessful = false;
				}
			}

		}
		return wasSuccessful;

	}

	public void readFile(String filename) {

		GraphFileReader.ladeDatei(filename);
		_edges = GraphFileReader.getEdges();
		_vertices = GraphFileReader.getNodes();

	}

	/**
	 * used for adjMatrix and getNeighbours
	 */
	public void createMatrix() {
		_matrix = new int[_vertices.size() + 1][_vertices.size() + 1];
		for (Edge egd : _edges) {
			int i = egd.getStart().getPos();

			int j = egd.getEnd().getPos();

			_matrix[i][j] = egd.getValue();
		}

	}

	public static void createList() {
		liste = new LinkedList[_edges.size()];
		int c = 0;
		for (int i = 1; i < liste.length; i++) {

			liste[i - 1] = new LinkedList<Edge>();

			for (Edge edges : _edges) {

				if (edges.getStart().getPos() == i) {

					liste[i - 1].add(_edges.get(c));

				}
				c++;
			}

			c = 0;

		}

	}

	public ArrayList<Vertice> getNeighbours(int key) {

		return _adjStructure.getNeighbours(key);
	}

	public boolean isConnected() {
		boolean flag = false;

		for (int i = 1; i <= _vertices.size(); i++) {
			if (this.getNeighbours(i).size() > 0) {
				flag = true;

			} else
				break;
		}
		return flag;
	}

	public LinkedList<Edge>[] getList() {
		return liste;
	}

	public int[][] getMatrix() {
		return _matrix;
	}

	public static void print() {
		_adjStructure.print();

	}

	public ArrayList<Edge> getEdges() {
		return _edges;
	}

	public Vertice getVertice(int value) {
		for (Vertice vertice : _vertices) {
			if (vertice.getPos() == value) {
				return vertice;
			}
		}
		return null;
	}

	public ArrayList<Vertice> getVertices() {
		return _vertices;
	}

	@Override
	public String toString() {
		System.out.println("" + getClass().getSimpleName()
				+ _adjStructure.getClass().getSimpleName());
		return super.toString();
	}

}
